package algorithm;

public class leetcode_0052 {
    public int totalNQueens(int n) {
        int[]num=new int[1];
        boolean[] lie=new boolean[n];
        boolean[] dia1=new boolean[2*n];
        boolean[] dia2=new boolean[2*n];
        int hang=0;
        dfs(num,lie,dia1,dia2,0,n);
        return num[0];
    }
    public void dfs(int[] num,boolean[] lie,boolean[] dia1,boolean[] dia2,int hang,int n){
        if(hang==n){
            num[0]++;
        }
        for(int i=0;i<n;++i){
            if(!lie[i]&&!dia1[hang-i+n]&&!dia2[hang+i]){
                lie[i]=true;
                dia1[hang-i+n]=true;
                dia2[hang+i]=true;
                dfs(num,lie,dia1,dia2,hang+1,n);
                lie[i]=false;
                dia1[hang-i+n]=false;
                dia2[hang+i]=false;
            }
        }
    }
}
